package LeetcodeTest_thirty_seven;

//576. 出界的路径数
public class findPaths
{
    public static void main(String[] args)
    {
        System.out.println(Solutions.findPaths(1,3,3,0,1));
    }
}
class Solutions
{
    public static int findPaths(int m, int n, int N, int i, int j)
    {
        long[][][] dp=new long[m+2][n+2][N+1];
        int answer=0;
        for(int k=0;k<m+2;k++)
        {
            dp[k][0][0]=1;
            dp[k][n+1][0]=1;
        }
        for(int k=0;k<n+2;k++)
        {
            dp[0][k][0]=1;
            dp[m+1][k][0]=1;
        }
        for(int k=1;k<N+1;k++)
        {
            for(int x=1;x<m+1;x++)
            {
                for(int y=1;y<n+1;y++)
                {
                    dp[x][y][k]=(dp[x-1][y][k-1]+dp[x+1][y][k-1]+dp[x][y-1][k-1]+dp[x][y+1][k-1])%1000000007;
                }
            }
        }
        for(int k=1;k<N+1;k++)
        {
            answer+=dp[i+1][j+1][k];
            answer%=1000000007;
        }
        return answer;
    }
}